package org.cagt.probability;


import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * Class implementing simple subsets generating algorithm. Generates modifiable
 * subsets of given collection.
 * 
 * @author konrad.szalkowski (at) gmail.com
 * 
 * @param <T>
 *            Type of elements inside the subsets.
 */
public class SubsetsSelector<T> implements ResetIterator<Set<T>> {
	private boolean[] elementIncluded;
	private Object[] vector;
	private int minSize;
	private int currentSize;
	private int maxSize;

	/**
	 * Standard constructor. Sets the algorithm to generate subsets of size from
	 * 0 to elements.size().
	 * 
	 * @param elements
	 *            Set of elements to generate subsets from.
	 */
	public SubsetsSelector(Collection<T> elements) {
		this(elements, 0, elements.size());
	}

	/**
	 * Standard constructor. Sets the algorithm to generate subsets of given
	 * size.
	 * 
	 * @param elements
	 *            Set of elements to generate subsets from.
	 * @param size
	 *            Size of possible subsets.
	 */
	public SubsetsSelector(Collection<T> elements, int size) {
		this(elements, size, size);
	}

	/**
	 * Standard constructor. Sets the algorithm to generate subsets of given
	 * size.
	 * 
	 * @param elements
	 *            Set of elements to generate subsets from.
	 * 
	 * @param minSize
	 *            Minimal size of subsets.
	 * @param maxSize
	 *            Maximal size of subsets.
	 */
	public SubsetsSelector(Collection<T> elements, int minSize, int maxSize) {
		if (elements == null) {
			throw new NullPointerException();
		}
		if (minSize < 0 || minSize > maxSize || maxSize > elements.size()) {
			throw new IllegalArgumentException();
		}
		// Init the vector and element included
		elementIncluded = new boolean[elements.size()];
		vector = elements.toArray();
		this.minSize = minSize;
		this.maxSize = maxSize;
		// Reset
		reset();
	}

	public int getMinSize() {
		return minSize;
	}

	public int getMaxSize() {
		return maxSize;
	}

	public int getCurrentSize() {
		return currentSize;
	}

	private void resetSize(int size) {
		if (currentSize > maxSize) {
			throw new NoSuchElementException();
		}
		// Fill with falses
		Arrays.fill(elementIncluded, false);
		// Fill first with trues
		Arrays.fill(elementIncluded, 0, size, true);
	}

	public void reset() {
		// Set current size
		currentSize = minSize - 1;
		// Set the reset size
		resetSize(minSize);
	}

	public boolean hasNext() {
		// Set iterator for last position
		int iterator = elementIncluded.length - 1;
		if (currentSize >= minSize && elementIncluded[iterator]) {
			// Count of passed trues
			int numberOfTruesPassed = 0;
			// Search for first false - count passing trues
			while (iterator >= 0 && elementIncluded[iterator]) {
				numberOfTruesPassed++;
				iterator--;
			}
			return iterator >= 0 && numberOfTruesPassed < maxSize;
		} else {
			return true;
		}
	}

	private void nextSetup() {
		// If current size is smaller than minimal it means that selector was
		// initialized - first setup is already there,if current size is greater
		// than max size no more elements
		if (currentSize > maxSize) {
			throw new NoSuchElementException();
		} else if (currentSize < minSize) {
			currentSize++;
			return;
		}
		// Count of passed trues
		int numberOfTruesPassed = 0;
		// Set iterator for last position
		int iterator = elementIncluded.length - 1;
		// If last element is true
		if (elementIncluded[iterator]) {
			// Search for first false - count passing trues
			while (iterator >= 0 && elementIncluded[iterator]) {
				numberOfTruesPassed++;
				iterator--;
			}
		}
		// If number of trues passed equals to current size increment it reset,
		// and start recurrently
		if (numberOfTruesPassed == currentSize) {
			currentSize++;
			resetSize(currentSize);
			return;
		}
		// Search for first true
		while (!elementIncluded[iterator] && iterator >= 0) {
			iterator--;
		}
		// False the first made true,
		elementIncluded[iterator] = false;
		numberOfTruesPassed++;
		iterator++;
		// Fill array after it with trues, after them with falses
		while (iterator < elementIncluded.length) {
			if (numberOfTruesPassed-- > 0) {
				elementIncluded[iterator] = true;
			} else {
				elementIncluded[iterator] = false;
			}
			iterator++;
		}
	}

	@SuppressWarnings("unchecked")
	public Set<T> next() {
		// Set the setup
		nextSetup();
		// Prepare the result
		Set<T> result = new HashSet<T>();
		for (int i = 0; i < elementIncluded.length; i++) {
			if (elementIncluded[i]) {
				result.add((T) vector[i]);
			}
		}
		return result;
	}
}
